Various techniques for routing packets through communication networks are known in the art. Some known techniques select routing paths for packets based on the network state, e.g., traffic load or congestion. Such techniques are sometimes referred to as Adaptive Routing (AR). For example, U.S. Pat. No. 6,950,428, whose disclosure is incorporated herein by reference, describes adaptive sets of lanes that are configured between routers in a system area network. Source nodes determine whether packets may be adaptively routed between the lanes by encoding adaptive control bits in the packet header. The adaptive control bits also facilitate the flushing of all lanes of the adaptive set. Adaptive sets may also be used in uplinks between levels of a fat tree.
As another example, U.S. Pat. No. 8,576,715, whose disclosure is incorporated herein by reference, describes a method for communication that includes routing a first packet, which belongs to a given packet flow, over a first routing path through a communication network. A second packet, which follows the first packet in the given packet flow, is routed using a time-bounded Adaptive Routing (AR) mode, by evaluating a time gap between the first and second packets, routing the second packet over the first routing path if the time gap does not exceed a predefined threshold, and, if the time gap exceeds the predefined threshold, selecting a second routing path through the communication network that is potentially different from the first routing path, and routing the second packet over the second routing path.
Adaptive routing may cause packets sent by a source to arrive at the destination in an order different from the transmission order. Techniques for preserving packet ordering are known in the art. For example, U.S. Pat. No. 8,774,063, whose disclosure is incorporated herein by reference, describes a method of preserving packet ordering in a multi-path network having a plurality of network elements interconnected by network links wherein for each data packet arriving at an egress port of the multi-path network, a delivery acknowledgement is issued by the egress port and is transmitted across the network following in reverse the path taken by the data packet being acknowledged, and wherein the state of each link in the path taken by the data packet being acknowledged is updated by the acknowledgement.